#include <bits/stdc++.h>
using namespace std;

/*
1931. 用三种不同颜色为网格涂色
已解答
困难
相关标签
相关企业
提示
给你两个整数 m 和 n 。构造一个 m x n 的网格，其中每个单元格最开始是白色。请你用 红、绿、蓝 三种颜色为每个单元格涂色。所有单元格都需要被涂色。

涂色方案需要满足：不存在相邻两个单元格颜色相同的情况 。返回网格涂色的方法数。因为答案可能非常大， 返回 对 109 + 7 取余 的结果。

 

示例 1：


输入：m = 1, n = 1
输出：3
解释：如上图所示，存在三种可能的涂色方案。
示例 2：


输入：m = 1, n = 2
输出：6
解释：如上图所示，存在六种可能的涂色方案。
示例 3：

输入：m = 5, n = 5
输出：580986
 

提示：

1 <= m <= 5
1 <= n <= 1000
 */

// 法一
/**
 * ​​状态压缩​​：由于每个单元格有3种颜色选择，且相邻单元格颜色不能相同，可以将每一列的颜色分布表示为一个三进制数（mask），其中每一位代表一个单元格的颜色（0、1、2）。
 * ​​预处理合法状态​​：枚举所有可能的三进制数，检查每一列的颜色是否合法（即相邻单元格颜色不同）。
​ * ​状态转移​​：使用动态规划，定义 dp[i][mask] 表示前i 列，且第 i 列的状态为 mask时的方案数。对于每一列，枚举所有可能的合法状态，并检查与前一列的状态是否冲突（即对应位置的颜色是否不同）。
​​ * 结果计算​​：最终结果是所有最后一列合法状态的方案数之和，并对10 ^ 9 +7 取余。
 */

class Solution {
public:
    int colorTheGrid(int m, int n) {
        const int MOD = 1e9 + 7;
        int max_mask = pow(3, m);
        vector<int> valid_masks;
        
        // 预处理所有合法的列状态
        for (int mask = 0; mask < max_mask; ++mask) {
            bool valid = true;
            int prev_color = -1;
            int temp = mask;
            for (int i = 0; i < m; ++i) {
                int color = temp % 3;
                if (color == prev_color) {
                    valid = false;
                    break;
                }
                prev_color = color;
                temp /= 3;
            }
            if (valid) {
                valid_masks.push_back(mask);
            }
        }
        
        // 预处理状态转移关系
        unordered_map<int, vector<int>> transitions;
        for (int mask1 : valid_masks) {
            for (int mask2 : valid_masks) {
                bool valid = true;
                int temp1 = mask1, temp2 = mask2;
                for (int i = 0; i < m; ++i) {
                    if (temp1 % 3 == temp2 % 3) {
                        valid = false;
                        break;
                    }
                    temp1 /= 3;
                    temp2 /= 3;
                }
                if (valid) {
                    transitions[mask1].push_back(mask2);
                }
            }
        }
        
        // 动态规划
        unordered_map<int, int> dp;
        for (int mask : valid_masks) {
            dp[mask] = 1;
        }
        for (int i = 1; i < n; ++i) {
            unordered_map<int, int> new_dp;
            for (auto [mask1, cnt] : dp) {
                for (int mask2 : transitions[mask1]) {
                    new_dp[mask2] = (new_dp[mask2] + cnt) % MOD;
                }
            }
            dp = move(new_dp);
        }
        
        // 计算结果
        int ans = 0;
        for (auto [mask, cnt] : dp) {
            ans = (ans + cnt) % MOD;
        }
        return ans;
    }
};

// 法二
class Solution {
public:
    static const int MOD = 1e9 + 7; // 定义模数，防止结果过大

    int colorTheGrid(int m, int n) {
        // 步骤1：生成所有合法的列状态
        vector<int> states; // 存储所有合法的列状态
        function<void(int, int)> dfs = [&](int row, int prev_color) {
            static int cur = 0; // 当前状态，用位运算存储颜色
            if (row == m) { // 如果已经处理完所有行
                states.push_back(cur); // 将当前状态加入合法状态列表
                return;
            }
            for (int c = 0; c < 3; ++c) { // 尝试三种颜色
                if (c == prev_color) continue; // 如果颜色与前一行相同，跳过
                cur |= (c << (2 * row)); // 将颜色c存储到当前行的位置（每行用2位表示）
                dfs(row + 1, c); // 递归处理下一行
                cur &= ~(3 << (2 * row)); // 回溯，清除当前行的颜色
            }
        };
        dfs(0, -1); // 从第0行开始，初始颜色为-1（表示无限制）

        // 步骤2：预处理状态转移关系（哪些状态可以相邻）
        int K = states.size(); // 合法状态的数量
        vector<vector<int>> compat(K); // 兼容性矩阵，compat[i]表示状态i可以转移到哪些状态
        for (int i = 0; i < K; ++i) {
            for (int j = 0; j < K; ++j) {
                int s1 = states[i], s2 = states[j]; // 取出两个状态
                bool ok = true; // 是否兼容
                for (int row = 0; row < m; ++row) { // 检查每一行
                    int c1 = (s1 >> (2 * row)) & 3; // 状态i的第row行颜色
                    int c2 = (s2 >> (2 * row)) & 3; // 状态j的第row行颜色
                    if (c1 == c2) { ok = false; break; } // 如果颜色相同，不兼容
                }
                if (ok) compat[i].push_back(j); // 如果兼容，记录状态j
            }
        }

        // 步骤3：动态规划计算方案数
        vector<int> dp(K, 1), ndp(K, 0); // dp[i]表示当前列状态为i的方案数
        for (int col = 2; col <= n; ++col) { // 从第2列开始处理
            fill(ndp.begin(), ndp.end(), 0); // 清空下一列的状态
            for (int i = 0; i < K; ++i) if (dp[i]) { // 遍历当前列的所有状态
                long long ways = dp[i]; // 当前状态的方案数
                for (int j : compat[i]) { // 遍历可以转移到的状态
                    ndp[j] = (ndp[j] + ways) % MOD; // 更新下一列的状态方案数
                }
            }
            dp.swap(ndp); // 更新当前列的状态
        }

        // 步骤4：统计最终结果
        int ans = 0;
        for (int x : dp) {
            ans = (ans + x) % MOD; // 将所有状态的方案数相加
        }
        return ans;
    }
    
};